﻿#define _CRT_SECURE_NO_WARNINGS 1

//121. 买卖股票的最佳时机
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // int n = prices.size();
        // int ret = 0, prevmin = INT_MAX;
        // for(int i = 0; i < n; ++i)
        // {
        //     ret = max(ret, prices[i] - prevmin);// 先更新结果
        //     prevmin = min(prevmin, prices[i]); // 在更新最⼩值
        // }
        // return ret;

        // 动态规划
        //dp[i] 表示: 前 i 天 价格最低点
        int n = prices.size(), ret = 0;
        vector<int> dp(n + 1);
        dp[0] = INT_MAX;
        for (int i = 1; i <= n; ++i)
        {
            ret = max(ret, prices[i - 1] - dp[i - 1]);
            dp[i] = min(dp[i - 1], prices[i - 1]);
        }
        return ret;
    }
};  